#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int memo[31];
    int fib(int n) {
        memset(memo, -1, sizeof(memo));
        memo[0] = 0;
        memo[1] = 1;
        return dfs(n);
    }
    int dfs(int n)
    {
        if (memo[n] != -1)
        {
            return memo[n];
        }
        if (n == 0 || n == 1)
        {
            return memo[n];
        }
        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }
};

class Solution {
public:
    int dp[31];
    int fib(int n) {
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};


class Solution {
public:

    int m, n;
    int ret = 0;
    vector<vector<int>> path;
    int uniquePaths(int _m, int _n) {
        m = _m;
        n = _n;
        path.resize(m);
        for (int i = 0; i < m; i++)
        {
            path[i].resize(n, -1);

        }
        return dfs(0, 0);
    }
    int dfs(int i, int j)
    {
        if (i == m || j == n)
            return 0;
        if (path[i][j] != -1)
        {
            return path[i][j];
        }
        if (i == m - 1 && j == n - 1)
        {
            return 1;
        }
        path[i][j] = dfs(i + 1, j) + dfs(i, j + 1);
        return path[i][j];
    }
};